1. Field of the Invention
This invention relates to a method of calculating the fast Fourier transform or the inverse fast Fourier transform of a series of real numbers or a series of conjugated complex samples.
2. Description of the Related Art
The Fourier transform is probably one of the most important tools for analyzing, designing and implementing signal processing algorithms, and the existence of efficient algorithms, such as that of the fast Fourier transform, has been a major factor for this situation. Although most Fourier transform algorithms are designed for transforming series of complex numbers, there are, however, various applications, such as image or acoustic signal processing or certain types of multicarrier modulation wherein the series to be transformed are real numbers.
In general, the direct Fourier transform and the inverse Fourier transform respectively set up the following relations between two series of N complex numbers, x(n) and X(n):             X      ⁡              (        n        )              =                                        ∑                          k              =              0                                      N              -              1                                ⁢                                    x              ⁡                              (                k                )                                      ⁢                          w              kn                        ⁢                                                   ⁢            with            ⁢                                                   ⁢            n                          ∈                              [                                          0                ⁢                                                                   ⁢                …                ⁢                                                                   ⁢                N                            -              1                        ]                    ⁢                                           ⁢          and          ⁢                                           ⁢                      w            kn                              =              ⅇ                              -            j                    ⁢                                           ⁢                                    2              ⁢              π              ⁢                                                           ⁢              kn                        N                                          x      ⁡              (        n        )              =                            1          N                ⁢                              ∑                          k              =              0                                      N              -              1                                ⁢                                    X              ⁡                              (                k                )                                      ⁢                          w                              -                kn                                      ⁢                                                   ⁢            with            ⁢                                                   ⁢            n                              ∈              [                              0            ⁢                                                   ⁢            …            ⁢                                                   ⁢            N                    -          1                ]            
In 1965, J. W. Cooley and J. W. Tukey described an algorithm allowing to rapidly calculate the Fourier transform of a series of N complex numbers in an article entitled “An Algorithm for the Machine Calculation of Complex Fourier Series”, Math. Computation, Vol. 19, 1965, pp. 297-301. This algorithm is very interesting when N is a power of two because it is then particularly straightforward to implement. This algorithm requires μ calculation steps where μ=log2(N). It is based on breaking down the series to be transformed into two interleaved sub-series. There are two kinds of interleaving: time interleaving and frequency interleaving. Both kinds of interleaving are explained more in detail in the course of the description with reference to FIGS. 1A and 1B.
Specific algorithms have been developed from this basic algorithm to deal with the case of real number series. The Fourier transformation of a series of 8 real numbers according to a time interleaving algorithm and according to a frequency interleaving algorithm is illustrated in FIGS. 1A and 1B. For each time interleaving Fourier transform algorithm there is a frequency interleaving algorithm, which corresponds to a double inversion of the series of transformation operations, on the one hand, and for each butterfly circuit, of the proper transformation operations, on the other hand. Whatever the interleaving chosen, the transformation method requires three transformation steps E0, E1, and E2, these steps being implemented through a set of four butterfly circuits CC, generally known as “butterflies” in technical speak. Each butterfly, represented in the figure by a point of intersection between two columns of numbers, performs calculations on two numbers, real or complex. The symbols R and C respectively identify a real number and a complex number. The sequence of real and/or complex numbers after the transformation steps depends on the interleaving chosen.
The time interleaving algorithm is generally chosen for calculating the Fourier transform of a series of real numbers because of the symmetrical distribution of real and complex numbers throughout the steps. On the other hand, the frequency interleaving algorithm is more suitable for the direct or inverse transformation of a series of conjugated complex numbers.
When the series to be transformed x(n) is real, the Fourier transform verifies the following relation:
x(n) is real if and only ifX(n)=X*(−n)=X*(N−n);  (1)where * designates the conjugating operation.
For a series x(n) of N real numbers, the following results are inferred from this relation:
−X(0) and X(N/2) are real;−X(n)=X*(N−n) for 1≦n≦N/2 −1
Relation (1) highlights the presence of redundant information in the X(n) series.
It should be noted that the transformation method is generally implemented by a single set of butterflies, the operating mode of which is modified as the transformation goes along. At each change of operating mode, results are stored in a memory having N storage locations, the output samples of a butterfly replacing the corresponding input samples of the same rank in the memory. This method of applying the algorithm is generally known as the “in place” method. This method has a major advantage: if the elements of the x(n) series are processed in the first transformation step in bit-reversed order of index n, the numbers of the X(n) series are output in the last transformation step in ascending order of index n and vice versa.
A known transformation method is shown by way of example in FIG. 2. This method performs the Fourier transformation of a real x(n) series according to a complex time interleaving algorithm. In this example, the x(n) series to be transformed comprises sixteen real samples, x(0) to x(15). The transformation method comprises four transformation steps Ep with 0≦p≦3. The samples of the x(n) series are shown in the first transformation step in bit-reversed order of their index n.
At this stage of the explanations, the terms used in the course of the description should be defined. The rank of a sample is taken from the position it occupies in the series of samples to which it belongs. The index of a sample then corresponds to the starting rank of this sample.
The intermediate results obtained in the various transformation steps are represented by the series A(n), B(n), and C(n). The samples of the series x(n), A(n), B(n), C(n), and X(n) are stored in double storage locations, one storage location being reserved for the real portion of the sample and the other location being reserved for the imaginary portion thereof. AR(n) and AI(n) respectively designate the real portion and the imaginary portion of the index n sample of the A(n) series. Butterflies are represented in the figure by points of intersection between columns of storage locations. Each butterfly is assigned a coefficient wS symbolized in FIG. 2 by a pair of coordinates A/B where A and B respectively designate the real portion and the imaginary portion of the coefficient WS. Coordinates 1/0 and 0/−1 are respectively assigned to coefficients W0=1 and WN/4=W4=−j. For the sake of clarity and in order to simplify their formulation, the remaining coefficients WS have been represented by the following pairs:                W1→2/−4        W2→3/−3        W3→4/−2        W5→−4/−2        W6→−3/−3        W7→−2/−4        
These pairs of coordinates are graphically represented in FIG. 3. In fact, coordinates A and B respectively represent a cosine value and a sine value. This coefficient WS participates in the calculation performed by the butterfly. Furthermore, the butterflies are distributed at each transformation step among N/2p+1 calculation blocks, each calculation block comprising 2p butterflies. In the course of the description, the parameter q designates the rank of the calculation blocks within the same transformation step; q is included between 0 and (N/2p+1)−1.
In the first transformation step E0, the butterflies are distributed among eight calculation blocks, each comprising a butterfly performing an operation on two complex or real samples. If e1 and e2 are to designate the samples applied to the inputs of a butterfly, the latter outputs samples s1 and S2 defined as follows:
 s1=e1+WS.e2 and s2=e1−(WS.e2)
where WS is the coefficient assigned to said butterfly.
For this first transformation step, coefficient W0=1 is assigned to the eight butterflies. As the samples x(n) and the coefficient W0 are real, the samples A(n) obtained at the end of step E0 are real.
For the second transformation step, E1, the butterflies are distributed among four calculation blocks each comprising two butterflies. Coefficient W0=1 is assigned to the first one of these butterflies; thus, the first butterfly of each calculation block provides two real samples. The second butterfly of the calculation blocks is associated with coefficient WN/4=W4=−j and generates two conjugated complex samples. The output samples obtained at the end of step E1 are designated by the series B(n).
For the third transformation step, E2, the butterflies are distributed among two calculation blocks each comprising four butterflies respectively associated with coefficients W0, W2, W4, and W6. The output samples in step E2 are designated by the series C(n). Finally, for the fourth transformation step, E3, a single calculation block comprising eight butterflies respectively associated with coefficients W0, W1, W2, W3, W4, W5, W6, and W7, is provided. This transformation step generates the transformed series X(n).
Given relation (1), the X(n) series comprises, on the one hand, real samples, X(0) and X(8), and on the other hand, complex samples, X(1) to X(7) and X(9) to X(15), samples X(15) to X(9) respectively being the conjugates of samples X(1) to X (7). The X(n) series therefore contains redundant information. The storage locations outlined in thick stroke in FIG. 2 designate the storage locations enclosing the conjugated values of the complex samples contained in the storage locations associated therewith by an arrow. The intermediate results series B(n) and C(n) also contain redundant information.
It is then possible to delete this redundant information in order to reduce by half the size of the sample storage memory as well as the number of butterflies.
However, removing redundant information stored in the storage locations outline in bold strokes in FIG. 2 implies the complete reorganization of the transformation steps of FIG. 2. Thus reorganizing the transformation has the effect of modifying the output sequence of samples X(n).
The problem therefore consists in reducing the size of the storage memory and the number of butterflies while maintaining the output sequence of the X(n) samples. It is the object of the invention to offer a method of calculating the fast Fourier transform or the inverse fast Fourier transform of a series of N real samples x(n), with N power of 2, operating according to a time interleaving algorithm, which provides the series of samples X(n) in ascending order of index n and uses limited calculation and storage means.